package algorithm.leetcode.medium;

/*
 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/20
 */
public class Question78 {

    public static void main(String[] args) {
        Question78 question = new Question78();
        int[] nums = {1,2,3};
        List<List<Integer>> subsets = question.subsets(nums);
        System.out.println(subsets);

    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(10);
        backtrack(0, nums, res, new ArrayList<>(10));
        return res;
    }


    private void backtrack(int i, int[] nums, List<List<Integer>> res, List<Integer> path) {
        res.add(new ArrayList<>(path));
        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            backtrack(j + 1, nums, res, path);
            path.remove(path.size() - 1);
        }
    }


}
